public class CountNumbersAlgorithm {

    /**
     * 给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。
     * <p>
     * 示例:
     * <p>
     * 输入: 2
     * 输出: 91
     * 解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/count-numbers-with-unique-digits
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */

    public static void main(String[] args) {
        CountNumbersAlgorithm numbersAlgorithm = new CountNumbersAlgorithm();
        int numbersWithUniqueDigits = numbersAlgorithm.countNumbersWithUniqueDigitsMax(4);
        System.out.println("输出:" + numbersWithUniqueDigits);
    }

    /**
     * 执行用时 :540 ms
     * 内存消耗 :36 MB
     */
    public int recursion(int n) {
        if (n == 0 || n == 1) {
            return 0;
        }
        if (n == 2) {
            return 9;
        }
        int pow = (int) Math.pow(10, n);
        int number = 0;
        int total = pow / 10 * 2;
        for (int i = (int) Math.pow(10, n - 1); i < total; i++) {
            String value = String.valueOf(i);
            for (int j = 0; j < value.length(); j++) {
                boolean isFlag = false;
                for (int k = j + 1; k < value.length(); k++) {
                    if (value.charAt(j) == value.charAt(k)) {
//                        if (String.valueOf(i).charAt(0) != '2') {
//                            continue;
//                        }
                        System.out.println(i);
                        number++;
                        isFlag = true;
                        break;
                    }
                }
                if (isFlag) {
                    break;
                }
            }
        }
        return number * 9 + recursion(n - 1);
    }

    public int countNumbersWithUniqueDigits(int n) {

        return ((int) Math.pow(10, n)) - recursion(n);
    }

    /**
     * n=0时，结果number=10;
     * n=1时，结果number=0+10;
     * n=2时，结果number=0+10+9*9=91;
     * n=3时，结果number=0+10+81+8*9*9=91+8*9*9=739;
     */
    public int countNumbersWithUniqueDigitsMax(int n) {
        int count = 0;
        switch (n) {
            case 0:
                count = 0;
                break;
            case 1:
                count = 10;
                break;
            case 2:
                count = 91;
                break;
            default:
                for (int i = 0; i < n; i--) {

                }
                count = 91 + 8 * ((int) Math.pow(9, n - 1));
                break;
        }
        return count;
    }

}
